\bigskip
\bigskip
{\magonebf 5.3 Planar Maps (planar\_map)}

{\bf 1. Definition}

An instance $M$ of the data type $planar\_map$ is the combinatorial
embedding of a planar graph.

\def\name{$planar\_map$}
\def\type{planar\_map}

\bigskip
{\bf 2. Creation}

\create M (graph\ G)

creates an instance $M$ of type $planar\_map$ and initializes it to 
the planar map represented by the directed graph $G$. \precond $G$ 
represents an undirected planar map, i.e. for every edge $(v,w)$ in $G$
the reverse edge $(w,v)$ is also in $G$ and there is a planar embedding
of $G$ such that for every node $v$ the ordering of the edges in the 
adjacency list of $v$ corresponds to the counter-clockwise ordering of
these edges around $v$ in the embedding. 


\bigskip
{\bf 3. Operations}
\medskip
Most operations are the same as for directed graphs. The following operations
are either additional or have different effects.
\medskip
\+\cleartabs & \hskip 2truecm & \hskip 5.5truecm &\cr
\+\op face       adj\_face  {edge\ e}
                               {returns the face of \var\ to the right of $e$.}
\smallskip
\+\op list\<face\> all\_faces {}
                               {returns the list of all faces of \var.}
\smallskip
\+\op list\<face\> adj\_faces {node\ v}
                               {returns the list of all faces of \var\ adjacent}
\+\nop                         {to node $v$ in counter-clockwise order.}
\smallskip
\+\op list\<edge\> adj\_edges {face\ f}
                               {returns the list of all edges of \var\ bounding}
\+\nop                         {face $f$ in clockwise order.}
\smallskip
\+\op list\<node\> adj\_nodes {face\ f}
                               {returns the list of all nodes of \var\ adjacent}
\+\nop                         {to face $f$ in clockwise order.}
\smallskip
\+\op edge       reverse   {edge\ e}
                                 {returns the reversal of edge $e$ in \var. }
\smallskip
\+\op edge       first\_face\_edge {}
                                 {returns the first edge of face $f$ in \var. }
\smallskip
\+\op edge       succ\_face\_edge {edge\ e}
                               {returns the successor edge of $e$ in face $f$}
\+\nop                         {i.e., the next edge in clockwise order.}
\smallskip
\+\op edge       pred\_face\_edge {edge\ e}
                              {returns the predecessor edge of $e$ in face $f$,}
\+\nop                        {i.e., the next edge in counter-clockwise order.}
\smallskip
\+\op edge new\_edge {edge\ e_1,\ edge\ e_2} {}
\+\nop                        {inserts the edge $e=(source(e_1),source(e_2))$}
\+\nop                        {and its reversal edge into $M$. \precond }
\+\nop                        {$e_1$ and $e_2$ are bounding the same face $F$.}
\+\nop                        {The operation splits $F$ into two new faces.}
\smallskip
\+\op edge del\_edge {edge\ e}
                              {deletes the edge $e$ from \var. The two faces}
\+\nop                        {adjacent to $e$ are united to one face.}
\smallskip
\+\op edge split\_edge {edge\ e}
                            {splits edge $e=(v,w)$ and its reversal $r=(w,v)$}
\+\nop                      {into edges $(v,u)$, $(u,w)$, $(w,u)$, and $(u,v)$.}
\+\nop                      {Returns the edge $(u,w)$. }
\smallskip
\+\op node new\_node {face\ f}
                           {splits face $f$ into triangles by inserting a new}
\+\nop                     {node $u$ and connecting it to all nodes of $f$. }
\+\nop                     {Returns $u$.}
\smallskip
\+\op node new\_node {list\<edge\>\ el}
                           {splits the face bounded by the edges in $el$ by}
\+\nop                     {inserting a new node $u$ and connecting it to all}
\+\nop                     {source nodes of edges in $el$. \precond}
\+\nop                     {all edges in $el$ bound the same face.}
\smallskip
\+\op list\<edge\> triangulate {}
                             {triangulates all faces of \var\ by inserting new}
\+\nop                       {edges. The list of inserted edges is is returned.}
\smallskip
\+\op int straight\_line\_embedding {node\_array(int)\ xcoord,\ node\_array(int)\ ycoord} {}
\+\nop                    {computes a straight line embedding for $M$ with}
\+\nop                    {integer coordinates $xcoord[v]$, $ycoord[v])$ in the}
\+\nop                    {range $0\dots 2(n-1)$ for every node $v$ of $M$,}
\+\nop                    {and returns the maximal used coordinate. }



\bigskip
{\bf 4. Iteration}

{\bf forall\_faces}($f,M$)  
$\{$ ``the faces of $M$ are successively assigned to $f$" $\}$

{\bf forall\_adj\_edges}($e,f$) \nl
\phantom{{\bf forall\_edges}($v,M$)}
$\{$ ``the edges adjacent to face f are successively assigned to e" $\}$

\bigskip
{\bf 5. Implementation}

Planar maps are implemented by parameterized directed graphs.
All operations take constant time, except of, new\_edge and del\_edge
which take time $O(f)$ where $f$ is the number of edges in the created
faces, and triangulate and straight\_line\_embedding take time $O(n)$
where $n$ is the current size (number of edges) of the planar map.

\vfill\eject

